/*************************************************************************
> File Name: separationAndAccumulation.cpp
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2024-01-15 22:00:15
> Description:
238. 除自身以外数组的乘积
给你一个整数数组 nums，返回 数组 right ，其中 right[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
************************************************************************/

// 思路：
// 把right[i]中记录索引值右边的乘积
// 索引左边乘积用变量left记录
// 两边相乘就是结果
// 返回right[i];
// tips : 注意边界值

#include <vector>
using namespace std;

class Solution
{
public:
    vector<int> productExceptSelf(vector<int> &nums)
    {
        int length = nums.size();
        vector<int> right(length);

        // right[i] 表示索引 i 右侧所有元素的乘积
        // 因为索引为 'length-1' 的元素右侧没有元素， 所以 right[length-1] = 1
        right[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--)
        {
            right[i] = nums[i + 1] * right[i + 1];
        }

        // left 为左侧所有元素的乘积
        // 刚开始左边没有元素，所以 R = 1
        int left = 1;
        for (int i = 0; i < length; i++)
        {
            // 对于索引 i，左边的乘积为 left，右边的乘积为 right[i]
            right[i] = right[i] * left;
            // left 需要包含左边所有的乘积，所以计算下一个结果时需要将当前值乘到 left 上
            left *= nums[i];
        }
        return right;
    }
};